package com.wu.serialize;

/**
 * 序列化二叉树
 */
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}

public class Solution {

    String Serialize(TreeNode root) {
        if (root == null) {
            return "";
        }
        return helpSerialize(root, new StringBuilder()).toString();
    }

    private StringBuilder helpSerialize(TreeNode root, StringBuilder s) {
        if (root == null) {
            return s;
        }
        s.append(root.val).append("!");
        if (root.left != null) {
            helpSerialize(root.left, s);
        } else {
            s.append("#!"); // 为null的话直接添加即可
        }
        if (root.right != null) {
            helpSerialize(root.right, s);
        } else {
            s.append("#!");
        }
        return s;
    }

    private int index = 0; // 设置全局主要是遇到了#号的时候需要直接前进并返回null

    // 1!2!4!#!#!5!#!#!3!6!#!#!7!#!#!
    TreeNode Deserialize(String str) {
        if (str == null || str.length() == 0) {
            return null;
        }
        String[] split = str.split("!");
        return helpDeserialize(split);
    }

    private TreeNode helpDeserialize(String[] strings) {
        if (strings[index].equals("#")) {
            index++;// 数据前进
            return null;
        }
        // 当前值作为节点已经被用
        TreeNode root = new TreeNode(Integer.valueOf(strings[index]));
        index++; // index++到达下一个需要反序列化的值
        root.left = helpDeserialize(strings);
        root.right = helpDeserialize(strings);
        return root;
    }
}
